package DataStructure.linkList;

/**
 * 876. 链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list
 * 题目简述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
 */
public class MiddleNode {

    /**
     * 思路：快慢指针。初始时slow和fast同指向head，然后slow一次走一步，fast一次走两步，fast走完了则slow在中间
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
            if (fast.next != null)
                fast = fast.next;
        }
        return slow;
    }

    public ListNode middleNode2(ListNode head) {
        int length = 0;
        ListNode p = head;
        while(p != null) {
            p = p.next;
            length++;
        }
        //偏右取中 length/2 + 1
        int mid = length/2 + 1;
        p = head;
        for(int i=1;i < mid;i++) {
            p = p.next;
        }
        return p;
    }
}



